﻿#pragma once

namespace hash_bucket
{
	template<class T>
	struct HashBucketNode
	{
		T _data;
		HashBucketNode<T>* _next;
		HashBucketNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{
		}
	};


	// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
	template<class K, class V, class KeyOfValue, class HF>
	class HashTable;

	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
	template <class K, class V, class ref, class ptr, class KeyOfValue, class HF>
	struct HBIterator
	{
		typedef HashTable<K, V, KeyOfValue, HF> HashTable;
		typedef HashBucketNode<V>* PNode;
		typedef HBIterator<K, V, ref, ptr, KeyOfValue, HF> Self;

		HBIterator(PNode pNode = nullptr, HashTable* pHt = nullptr)
			:_pNode(pNode)
			,_pHt(pHt)
		{}

		HBIterator(PNode pNode = nullptr, const HashTable* pHt = nullptr)
			:_pNode(pNode)
			,_pHt(pHt)
		{
		}

		template<class K, class T, class ref, class ptr, class KeyOfValue, class HF>
		HBIterator(const HBIterator<K, T, ref, ptr, KeyOfValue, HF>& it)
			:_pNode(it._pNode)
			, _pHt(it._pHt)
		{
		}

		
		
		Self& operator++()
		{
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			if (_pNode->_next)
				_pNode = _pNode->_next;
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				size_t ky = HF()(KeyOfValue()(_pNode->_data)) % _pHt->_tables.size() + 1;
				for (; ky < _pHt->_tables.size(); ++ky)
				{
					if (_pNode = _pHt->_tables[ky])
						break;
				}
				if (ky == _pHt->_tables.size())
				{
					_pNode = nullptr;
				}
			}

			return *this;
		}
		Self operator++(int) {
			auto tmp = *this;
			this->operator++();
			return tmp;
		}
		ref operator*() {
			return _pNode->_data;
		}
		ptr operator->() {
			return &(_pNode->_data);
		}
		bool operator==(const Self& it) const {
			return (it._pNode == _pNode) && (it._pHt == _pHt);
		}
		bool operator!=(const Self& it) const {
			return (it._pNode != _pNode) || (it._pHt != _pHt);
		}
		PNode _pNode;             // 当前迭代器关联的节点
		const HashTable* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
	};


	template<class K>
	struct HashFunc {
	public:
		size_t operator()(const K& key) {
			return (size_t)key;
		}
	};

	template<>
	struct HashFunc<string> {
	public:
		size_t operator()(const string& key) {
			size_t ky = 0;
			for (auto& e : key) {
				ky *= 31;
				ky += e;
			}
			return ky;
		}
	};


	// K 为 T 中key的类型
	// T 可能是键值对，也可能是K
	// KeyOfT: 从T中提取key
	// Hash将key转化为整形，因为哈市函数使用除留余数法
	template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
	class HashTable
	{
		template <class K, class V, class ref, class ptr, class KeyOfValue, class HF>
		friend struct HBIterator;
		typedef HashBucketNode<T> Node;
	public:
		typedef HBIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
		typedef HBIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		// 哈希桶的销毁
		~HashTable() {
			for (size_t i = 0; i < _tables.size(); i++) {
				Node* cur = _tables[i];
				while (cur) {
					Node* tmp = cur->_next;
					delete cur;
					_n--;
					cur = tmp;
				}
				_tables[i] = nullptr;
			}
		}

		iterator begin() {
			for (size_t i = 0; i < _tables.size(); i++) {
				if (_tables[i]) return iterator(_tables[i], this);
			}
			return iterator(nullptr, this);
		}

		iterator end() {
			return iterator(nullptr, this);
		}

		const_iterator begin() const{
			for (size_t i = 0; i < _tables.size(); i++) {
				if (_tables[i]) return const_iterator(_tables[i], this);
			}
			return const_iterator(nullptr, this);
		}

		const_iterator end() const{
			return const_iterator(nullptr, this);
		}

		size_t size() const{
			return _n;
		}

		bool empty() const{
			return _n == 0;
		}

		size_t Count(const K& key)  {
			Hash hs;
			KeyOfT kot;
			size_t ky = hs(key) % _tables.size();

			Node* cur = _tables[ky];
			size_t count = 0;
			while (cur) {
				count++;
				cur = cur->_next;
			}
			return count;
		}

		size_t BucketCount() {
			return _tables.size();
		}

		size_t BucketSize(const K& key) {
			return Count(key);
		}

		// 插入值为data的元素，如果data存在则不插入
		pair<iterator, bool> Insert(const T& data) {
			KeyOfT kot;
			Hash hs;
			iterator it = Find(kot(data));
			if (it._pNode != nullptr) return make_pair(it, false);
			if (_n == _tables.size()) {
				HashTable tmp;
				tmp._tables.resize(2 * _tables.size(),nullptr);
				for (size_t i = 0; i < _tables.size(); i++) {
					Node* cur = _tables[i];
					while (cur) {
						Node* tp = cur->_next;
						//计算cur在新表中的位置
						size_t hashi = hs(kot(cur->_data)) % tmp._tables.size();
						cur->_next = tmp._tables[hashi];
						tmp._tables[hashi] = cur;
						cur = tp;
						tmp._n++;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(tmp._tables);
			}
			size_t ky = hs(kot(data)) % _tables.size();
			Node* tmp = new Node(data);
			tmp->_next = _tables[ky];
			_tables[ky] = tmp;
			_n++;
			return make_pair(iterator(tmp, this), true);
		}

		// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
		iterator Find(const K& key) {
			Hash hs;
			KeyOfT kot;
			size_t ky = hs(key) % _tables.size();

			Node* cur = _tables[ky];
			while (cur) {
				if (kot(cur->_data) == key) {
					return iterator(cur, this);
				}
				cur = cur->_next;
			}
			return iterator(nullptr, this);
		}

		// 哈希桶中删除key的元素，删除成功返回true，否则返回false
		iterator Erase(iterator position) {
			K key = KeyOfT()(position._pNode->_data);
			iterator it = Find(key);
			if (it._pNode == nullptr) return it;
			Hash hs;
			KeyOfT kot;
			size_t ky = hs(key);
			Node* cur = _tables[ky];
			if (kot(cur->_data) == key) {
				delete cur;
				_tables[ky] = nullptr;
				_n--;
				while (ky < _tables.size() && !_tables[ky]) ky++;
				if (ky == _tables.size()) return iterator(nullptr, this);
				return iterator(_tables[ky], this);
			}
			Node* prev = cur;
			while (cur) {
				if (kot(cur->_data) == key) {
					prev->_next = cur->_next;
					delete cur;
					_n--;
					if (!prev->_next) {
						ky++;
						while (ky<_tables.size() && !_tables[ky]) ky++;
						if (ky == _tables.size()) break;
						return iterator(_tables[ky], this);
					}
					return iterator(prev->_next, this);
				}
				prev = cur;
				cur = cur->_next;
			}
			return iterator(nullptr, this);
		}

		void Print() {
			for (auto& e : _tables) {
				Node* tmp = e;
				while (tmp) {
					cout << tmp->_data << " ";
					tmp = tmp->_next;
				}
			}
			cout << endl;
		}

	private:
		vector<Node*> _tables;  // 指针数组
		size_t _n = 0;			// 表中存储数据个数
	};
}